package now_coder.greedy.solutions;

import java.util.Arrays;
import java.util.PriorityQueue;

public class NCSolution147 {

    /*
     * 主持人调度
     *
     * 首先对活动的开始时间与结束时间进行排序：
     *
     * 1.当开始时间相等时，结束时间早的排在前面
     * 2.当开始时间不等时，开始时间早的排在前面
     *
     * 接着使用一个优先队列 PriorityQueue（小根堆）来保存最先结束的活动时间，当有新的活动时，如果这个活动的结束时间 end[i] 大于堆顶元素
     * 的结束时间，那么就说明主持人在主持完堆顶的元素表示的活动之后，可以继续主持当前活动。于是把堆顶元素删除掉，再把当前活动元素的结束时间
     * 添加到栈顶中。
     */

    public int minmumNumberOfHost (int n, int[][] startEnd) {
        if(n <= 1){
            return n;
        }
        // 首先安装开始时间排序，开始时间相等的按照截至时间排序
        Arrays.sort(startEnd , (o1 , o2) -> {
            return o1[0] ==  o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
        });
        // 保存每一个时间段的终止时间，从小到大
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0 ; i < n ; i++){
            // 若当前时间段的开始时间大于了队首的终止时间，那么队首的主持人可以继续主持这个，不用加人
            if(!queue.isEmpty() && queue.peek() <= startEnd[i][0]){
                queue.poll();
            }
            queue.offer(startEnd[i][1]);
        }
        return queue.size();
    }

}
